44. The
number of ones
In arithmetic expression you
are allowed to use the number 1, operations of addition, multiplication and
parenthesis. What is the minimum number of ones you need to obtain the positive
integer n?
Input. One number n
(1 ≤ n ≤ 5000).
Output. The required number of ones.
|
Sample input |
Sample output |
|
7 |
6 |
SOLUTION
dynamic
programming
Algorithm analysis
Let f(n) equals
to the smallest number of ones, with which you can get a number n. Obviously that f(1) = 1.
Number 2 can only be represented as the sum of two ones:
2 = 1 + 1. Therefore, f(2) = 2. Number 3 can only be represented as the sum of
three ones: 3 = 1 + 1 + 1. Therefore, f(3) = 3.
Number 4 can be represented either as 4 = 1 + 1 + 1 +
1, or 4 = (1 + 1) * (1 + 1). However, in both cases, 4 ones are used. Hence f(4)
= 4.
Consider the required expression with result n.
1. Let the last executed operation be addition. Let for
example, the first term i contains f(i) ones, and the second term n – i
contains f(n – i) ones. The value of i must
be chosen so that the sum f(i) + f(n – i)
is minimized.
The value of i
is enough to iterate up to n / 2, since
it can be assumed that the first term is not greater than the second one. Thus
we have the relation:
f(n) = 
2. Let the last executed operation in expression was
multiplication. Let for example, the first term i contains f(i) ones, and
the second term n / i contains f(n / i) ones. This case
occurs if n is divisible by i.
The value of i
must be chosen so that the sum f(i) +
f(n / i) is minimized. The value of i
is enough to iterate up to 
. Thus we have the relation:
f(n) = 
So
f(n) = 
Example
Compute the answer for n = 7:
f(7) = f(6) + f(1) = (f(2) + f(3)) + f(1) = 2 + 3 + 1 = 6
Number 7 can be represented with 6 ones:
7 = (1 + 1) * (1 + 1 + 1) + 1
Algorithm realization
Declare the array res[5001], initialize res[1] with 1.
int res[5001];
scanf("%d",&n);
res[1]
= 1;
Then sequentially compute
the values res[2], res[3], …, res[n]
according to the formula above.
for(i =
2; i <= n; i++)
{
res[i] = i;
for(j = 1; 2
* j < i; j++)
if (res[j]
+ res[i-j] < res[i]) res[i] = res[j] + res[i-j];
for(j = 2; j
* j <= i; j++)
if (i % j
== 0)
if
(res[j] + res[i/j] < res[i]) res[i] = res[j] + res[i/j];
}
Print the answer.
printf("%d\n",res[n]);
Algorithm realization – recursion with memoization
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 2000000000
using namespace
std;
int n;
int dp[5001];
int f(int
n)
{
if (n == 1) return 1;
if (dp[n] != -1) return
dp[n];
int res = INF;
for(int i = 1; i
<= n / 2; i++)
res = min(res,f(i)
+ f(n - i));
for(int i = 2; i * i
<= n; i++)
if (n % i == 0) res = min(res,f(i) + f(n/i));
return dp[n] = res;
}
int main(void)
{
memset(dp,-1,sizeof(dp));
scanf("%d",&n);
printf("%d\n",f(n));
return 0;
}
Java
realization
import java.util.*;
public class Main
{
public static int MAX = 5001;
static int res[] = new int[MAX];
public static void main(String[] args)
{
Scanner con = new
Scanner(System.in);
int n = con.nextInt();
res[1] = 1;
for(int i = 2; i <= n; i++)
{
res[i] = i;
for(int j = 1; 2 * j < i; j++)
if (res[j] + res[i-j] < res[i]) res[i] = res[j] + res[i-j];
for(int j = 2; j * j <= i; j++)
if (i % j == 0)
if (res[j] + res[i/j] < res[i]) res[i] = res[j] + res[i/j];
}
System.out.println(res[n]);
con.close();
}
}